/*********************************************************************
 *
 * CHINA TELECOM CORPORATION CONFIDENTIAL
 * ______________________________________________________________
 *
 *  [2015] - [2020] China Telecom Corporation Limited, 
 *  All Rights Reserved.
 *
 * NOTICE:  All information contained herein is, and remains
 * the property of China Telecom Corporation and its suppliers,
 * if any. The intellectual and technical concepts contained 
 * herein are proprietary to China Telecom Corporation and its 
 * suppliers and may be covered by China and Foreign Patents,
 * patents in process, and are protected by trade secret  or 
 * copyright law. Dissemination of this information or 
 * reproduction of this material is strictly forbidden unless prior 
 * written permission is obtained from China Telecom Corporation.
 **********************************************************************/
package com.shujia.common.utils.poly;

import com.shujia.common.utils.Geography;
import com.shujia.common.utils.Grid;

import java.awt.geom.GeneralPath;
import java.awt.geom.Point2D;
import java.util.*;


/**
 * 几何模型 多边形
 *
 * @author dingjingbo
 */
public class Polygon {
    private Point2D.Double peakPoint;
    private GeneralPath generalPath;
    private List<Point2D.Double> boundary;
    private List<Point2D.Double> boundaryConvert;

    /**
     * 构造方法
     */
    public Polygon() {
        super();
    }

    /**
     * 构造方法
     *
     * @param boundary 边界点（经纬度）
     */
    public Polygon(List<Point2D.Double> boundary) {
        super();
        init(boundary);
    }

    /**
     * 构造方法
     *
     * @param boundary 边界点（经纬度）
     */
    public Polygon(String boundary) {
        this(DataFormatUtil.stringBoundary2List(boundary));
    }

    private void init(List<Point2D.Double> boundary) {
        this.boundary = boundary;
        List<Point2D.Double> points = new ArrayList<Point2D.Double>();
        int i = 0;
        for (Point2D.Double point : boundary) {
            i++;
            if (i == 1) {
                this.peakPoint = point;
            }
            points.add(Geography.longilati2Decare(peakPoint, point));
        }
        this.boundaryConvert = points;
        drawMyself();
    }

    public Polygon(Circle circle) {
        List<Point2D.Double> points = new ArrayList<Point2D.Double>();
        for (int i = 0; i < 360; i++) {
            double val = 111319.55 * Math.cos(circle.getP().y * Math.PI / 180);
            double lon = circle.getP().x + (circle.getR() * Math.sin(i * Math.PI / 180)) / val;
            double lat = circle.getP().y + (circle.getR() * Math.cos(i * Math.PI / 180)) / 111133.33;
            points.add(new Point2D.Double(lon, lat));
        }
        init(points);
    }

    public void setPeakPoint(Point2D.Double peakPoint) {
        this.peakPoint = peakPoint;
    }

    public Point2D.Double getPeakPoint() {
        return peakPoint;
    }

    public GeneralPath getGeneralPath() {
        return generalPath;
    }

    public List<Point2D.Double> getBoundary() {
        return boundary;
    }

    /**
     * 设置多边形边界点
     *
     * @param boundary 边界点（经纬度）
     */
    public void setBoundary(List<Point2D.Double> boundary) {
        init(boundary);
    }

    public List<Point2D.Double> getBoundaryConvert() {
        return boundaryConvert;
    }

    /**
     * 构建多边形
     */
    public void drawMyself() {
        GeneralPath p = new GeneralPath();

        Point2D.Double first = boundaryConvert.get(0);
        p.moveTo(first.x, first.y);

        for (int i = 1; i < boundaryConvert.size(); i++) {
            p.lineTo(boundaryConvert.get(i).x, boundaryConvert.get(i).y);
        }
        p.lineTo(first.x, first.y);

        p.closePath();

        this.generalPath = p;
    }

    /**
     * 计算面积
     *
     * @return 面积（平方米）
     */
    public double getArea() {
        return Math.abs(getSignedArea());
    }

    /**
     * 计算有向面积
     *
     * @return 面积（平方米）
     */
    public double getSignedArea() {
        //S = 0.5 * ( (x0*y1-x1*y0) + (x1*y2-x2*y1) + ... + (xn*y0-x0*yn) )
        double area = 0.00;
        for (int i = 0; i < boundaryConvert.size(); i++) {
            if (i < boundaryConvert.size() - 1) {
                Point2D.Double p1 = boundaryConvert.get(i);
                Point2D.Double p2 = boundaryConvert.get(i + 1);
                area += p1.getX() * p2.getY() - p2.getX() * p1.getY();
            } else {
                Point2D.Double pn = boundaryConvert.get(i);
                Point2D.Double p0 = boundaryConvert.get(0);
                area += pn.getX() * p0.getY() - p0.getX() * pn.getY();
            }
        }
        area = area / 2.00;
        return area;
    }

    /**
     * 内部随机点
     *
     * @return 随机点
     */
    public Point2D.Double randomPoint() {
        //找出包含多边形的矩形的四个端点
        double maxLongi = 0d;
        double minLongi = Double.MAX_VALUE;
        double maxLati = 0d;
        double minLati = Double.MAX_VALUE;
        for (Point2D.Double point : boundary) {
            if (point.getX() < minLongi) {
                minLongi = point.getX();
            }
            if (point.getX() > maxLongi) {
                maxLongi = point.getX();
            }
            if (point.getY() < minLati) {
                minLati = point.getY();
            }
            if (point.getY() > maxLati) {
                maxLati = point.getY();
            }
        }
        //随机一个在里面的点
        while (true) {
            Point2D.Double randomPoint = nextRandomPoint(maxLongi, minLongi, maxLati, minLati);
            if (randomPoint != null && contains(randomPoint)) {
                return randomPoint;
            }
        }
    }

    /**
     * 内部随机点
     *
     * @return 随机点
     */
    public Point2D.Double randomPoint(double seedLongi, double seedLati) {
        //找出包含多边形的矩形的四个端点
        double maxLongi = 0d;
        double minLongi = Double.MAX_VALUE;
        double maxLati = 0d;
        double minLati = Double.MAX_VALUE;
        for (Point2D.Double point : boundary) {
            if (point.getX() < minLongi) {
                minLongi = point.getX();
            }
            if (point.getX() > maxLongi) {
                maxLongi = point.getX();
            }
            if (point.getY() < minLati) {
                minLati = point.getY();
            }
            if (point.getY() > maxLati) {
                maxLati = point.getY();
            }
        }
        //随机一个在里面的点
        while (true) {
            Point2D.Double randomPoint = nextRandomPoint(seedLongi, seedLati, maxLongi, minLongi, maxLati, minLati);
            if (randomPoint != null && contains(randomPoint)) {
                return randomPoint;
            }
        }
    }

    /**
     * 获取内切圆向外扩大指定范围的圆
     *
     * @param length 扩大范围，单位m
     * @return
     */
    public Circle enlarge(double length) {
        double maxLongi = 0d;
        double minLongi = Double.MAX_VALUE;
        double maxLati = 0d;
        double minLati = Double.MAX_VALUE;
        for (Point2D.Double point : boundary) {
            if (point.getX() < minLongi) {
                minLongi = point.getX();
            }
            if (point.getX() > maxLongi) {
                maxLongi = point.getX();
            }
            if (point.getY() < minLati) {
                minLati = point.getY();
            }
            if (point.getY() > maxLati) {
                maxLati = point.getY();
            }
        }
        double centerLongi = (minLongi + maxLongi) / 2;
        double centerLati = (minLati + maxLati) / 2;
        double r = Geography.calculateLength(minLongi, maxLati, maxLongi, minLati) / 2;
        return new Circle(centerLongi, centerLati, r + length);
    }

    /**
     * 根据重心等比例扩大指定范围
     *
     * @param m 扩大范围，单位米
     * @return
     */
    public Polygon enlargeM(double len) {
        List<Point2D.Double> points = new ArrayList<Point2D.Double>();
        Point2D.Double gravityPoint = getGravityPoint();
        Point2D.Double gravityPointDecare = Geography.longilati2Decare(this.getPeakPoint(), gravityPoint);
        double maxlength = 0d;
        for (int i = 0; i < this.boundary.size(); i++) {
            double length = Geography.calculateLength(gravityPoint.x, gravityPoint.y, this.boundary.get(i).x, this.boundary.get(i).y);
            if (length > maxlength) {
                maxlength = length;
            }
        }
        double minMultiple = len / maxlength;
        for (int i = 0; i < this.boundary.size(); i++) {
            Geography.longilati2Decare(getGravityPoint(), this.boundary.get(i));
            Point2D.Double pointDecare = Geography.longilati2Decare(this.getPeakPoint(), this.boundary.get(i));
            Line line = new Line(gravityPointDecare, pointDecare);
            double x = minMultiple * (pointDecare.x - gravityPointDecare.x) + pointDecare.x;
            if (CommonUtil.between(x, gravityPointDecare.x, pointDecare.x)) {
                x = -minMultiple * (pointDecare.x - gravityPointDecare.x) + pointDecare.x;
            }
            double y = line.getY(x);
            Point2D.Double decare2Longilati = Geography.decare2Longilati(this.getPeakPoint(), new Point2D.Double(x, y));
            points.add(decare2Longilati);
        }
        return new Polygon(points);
    }

    /**
     * 根据重心等距距扩大指定范围
     *
     * @param m 扩大范围，单位米
     * @return
     */
    public Polygon enlargeN(double len) {
        List<Point2D.Double> points = new ArrayList<Point2D.Double>();
        Point2D.Double gravityPoint = getGravityPoint();
        Point2D.Double gravityPointDecare = Geography.longilati2Decare(this.getPeakPoint(), gravityPoint);
        for (int i = 0; i < this.boundary.size(); i++) {
            double length = Geography.calculateLength(gravityPoint.x, gravityPoint.y, this.boundary.get(i).x, this.boundary.get(i).y);
            double minMultiple = len / length;
            Geography.longilati2Decare(getGravityPoint(), this.boundary.get(i));
            Point2D.Double pointDecare = Geography.longilati2Decare(this.getPeakPoint(), this.boundary.get(i));
            Line line = new Line(gravityPointDecare, pointDecare);
            double x = minMultiple * (pointDecare.x - gravityPointDecare.x) + pointDecare.x;
            if (CommonUtil.between(x, gravityPointDecare.x, pointDecare.x)) {
                x = -minMultiple * (pointDecare.x - gravityPointDecare.x) + pointDecare.x;
            }
            double y = line.getY(x);
            Point2D.Double decare2Longilati = Geography.decare2Longilati(this.getPeakPoint(), new Point2D.Double(x, y));
            points.add(decare2Longilati);
        }
        return new Polygon(points);
    }

    /**
     * 获取多边形重心点
     *
     * @return
     */
    public Point2D.Double getGravityPoint() {
        double area = 0.0;//多边形面积
        double Gx = 0.0, Gy = 0.0;// 重心的x、y
        for (int i = 1; i <= this.boundary.size(); i++) {
            double iLat = this.boundary.get(i % this.boundary.size()).y;
            double iLng = this.boundary.get(i % this.boundary.size()).x;
            double nextLat = this.boundary.get(i - 1).y;
            double nextLng = this.boundary.get(i - 1).x;
            double temp = (iLat * nextLng - iLng * nextLat) / 2.0;
            area += temp;
            Gx += temp * (iLat + nextLat) / 3.0;
            Gy += temp * (iLng + nextLng) / 3.0;
        }
        Gx = Gx / area;
        Gy = Gy / area;
        if (area - 0 < 0.0000001) {
            return getCenterPointX();
        }
        return new Point2D.Double(Gy, Gx);
    }

    /**
     * 根据输入的地点坐标计算中心点
     *
     * @return
     */
    public Point2D.Double getCenterPointX() {
        int total = this.boundary.size();
        double X = 0, Y = 0, Z = 0;
        for (Point2D.Double g : this.boundary) {
            double lat, lon, x, y, z;
            lat = g.y * Math.PI / 180;
            lon = g.x * Math.PI / 180;
            x = Math.cos(lat) * Math.cos(lon);
            y = Math.cos(lat) * Math.sin(lon);
            z = Math.sin(lat);
            X += x;
            Y += y;
            Z += z;
        }
        X = X / total;
        Y = Y / total;
        Z = Z / total;
        double Lon = Math.atan2(Y, X);
        double Hyp = Math.sqrt(X * X + Y * Y);
        double Lat = Math.atan2(Z, Hyp);
        return new Point2D.Double(Lon * 180 / Math.PI, Lat * 180 / Math.PI);
    }

    /**
     * 根据输入的地点坐标计算中心点（适用于400km以下的场合）
     *
     * @return
     */
    public Point2D.Double getCenterPointS() {
        //以下为简化方法（400km以内）
        int total = this.boundary.size();
        double lat = 0, lon = 0;
        for (Point2D.Double g : this.boundary) {
            lat += g.y * Math.PI / 180;
            lon += g.x * Math.PI / 180;
        }
        lat /= total;
        lon /= total;
        return new Point2D.Double(lon * 180 / Math.PI, lat * 180 / Math.PI);
    }

    /**
     * 随机生成一个矩形内的点
     *
     * @param maxLongi 最大经度
     * @param minLongi 最小经度
     * @param maxLati  最大纬度
     * @param minLati  最小纬度
     * @return 矩形内的随机点
     */
    private Point2D.Double nextRandomPoint(double maxLongi, double minLongi,
                                           double maxLati, double minLati) {
        int a = 100000000;
        int r1 = Math.abs((int) ((maxLongi - minLongi) * a));
        int r2 = Math.abs((int) ((maxLati - minLati) * a));
        Random randomLongi = new Random();
        Random randomLati = new Random();
        int nextInt1 = randomLongi.nextInt(r1);
        int nextInt2 = randomLati.nextInt(r2);
        double nextLongi = Double.parseDouble(nextInt1 + ".0") / a;
        double nextLati = Double.parseDouble(nextInt2 + ".0") / a;
        return new Point2D.Double(minLongi + nextLongi, minLati + nextLati);
    }

    /**
     * 随机生成一个矩形内的点 靠近种子点分布
     *
     * @param seedLongi 种子点经度
     * @param seedLati  种子点纬度
     * @param maxLongi  最大经度
     * @param minLongi  最小经度
     * @param maxLati   最大纬度
     * @param minLati   最小纬度
     * @return
     */
    public Point2D.Double nextRandomPoint(double seedLongi, double seedLati, double maxLongi, double minLongi,
                                          double maxLati, double minLati) {
        Point2D.Double point = nextRandomPoint(maxLongi, minLongi, maxLati, minLati);
        double maxLength = Geography.calculateLength(maxLongi, maxLati, minLongi, minLati);
        double length = Geography.calculateLength(seedLongi, seedLati, point.x, point.y);
        double df = 1 / maxLength;//权重衰减因子，每米点的密度衰减
        Random random = new Random();
        int nextInt = random.nextInt(10);
        if (nextInt < (1 - length * df) * 10) {
            return point;
        } else {
            return null;
        }
    }

    /**
     * 是否包含一个点
     *
     * @param point 点
     * @return 是否包含
     */
    public boolean contains(Point2D.Double point) {
        Point2D.Double convertCoord = Geography.longilati2Decare(peakPoint, point);
        return this.getGeneralPath().contains(convertCoord);
    }

    /**
     * 是否包含一个点
     *
     * @param x 经度
     * @param y 纬度
     * @return 是否包含
     */
    public boolean contains(double x, double y) {
        Point2D.Double convertCoord = Geography.longilati2Decare(peakPoint, new Point2D.Double(x, y));
        return this.getGeneralPath().contains(convertCoord.x, convertCoord.y);
    }

    /**
     * 是否包含一个点
     *
     * @return 是否包含
     */
    public boolean contains(Long grid) {

        Point2D.Double point1 = Grid.getCenter(grid);

        Point2D.Double convertCoord = Geography.longilati2Decare(peakPoint, new Point2D.Double(point1.x, point1.y));
        return this.getGeneralPath().contains(convertCoord.x, convertCoord.y);
    }

    /**
     * 判断一个多边形是否包含另一个多边形
     *
     * @param polygon
     * @return
     */
    public boolean contains(Polygon polygon) {
        for (Point2D.Double p : polygon.getBoundary()) {
            if (!this.contains(p)) {
                return false;
            }
        }
        return true;
    }

    public boolean contains(Circle circle) {
        return !circle.intersect(this) && this.contains(circle.getP());
    }

    /**
     * 是否与另外一个多变形相交
     *
     * @param polygon 多边形
     * @return 是否相交
     */
    public boolean intersect(Polygon polygon) {
        if (!contains(polygon) && !polygon.contains(this)) {
            for (Point2D.Double p : polygon.getBoundary()) {
                if (this.contains(p)) {
                    return true;
                }
            }
            for (Point2D.Double p : this.getBoundary()) {
                if (polygon.contains(p)) {
                    return true;
                }
            }
            for (int m = 0; m < polygon.getBoundary().size() - 1; m++) {
                Point2D.Double points = polygon.getBoundary().get(m);
                Point2D.Double pointe = polygon.getBoundary().get(m + 1);
                Set<Point2D.Double> intersectPoints = intersectPoints(points, pointe);
                if (!intersectPoints.isEmpty()) {
                    return true;
                }
            }
            return false;
        } else {
            return false;
        }

    }

    /**
     * 计算一个多边形与另一个多边形相交面积
     *
     * @param polygon
     * @return
     */
    public double intersectArea(Polygon polygon) {
        Polygon intersectPolygon = intersectPolygon(polygon);
        return intersectPolygon == null ? 0 : intersectPolygon.getArea();
    }

    /**
     * 计算一个多边形与另一个多边形相交面积
     *
     * @param polygon
     * @return
     */
    public Polygon intersectPolygon(Polygon polygon) {
        if (contains(polygon)) {
            return polygon;
        } else if (polygon.contains(this)) {
            return this;
        } else if (!intersect(polygon)) {
            return null;
        }
        Set<Point2D.Double> intersectPoints = new HashSet<Point2D.Double>();
        for (int m = 0; m < polygon.getBoundary().size() - 1; m++) {
            Point2D.Double points = polygon.getBoundary().get(m);
            Point2D.Double pointe = polygon.getBoundary().get(m + 1);
            intersectPoints.addAll(intersectPoints(points, pointe));
        }
        Point2D.Double points = polygon.getBoundary().get(polygon.getBoundary().size() - 1);
        Point2D.Double pointe = polygon.getBoundary().get(0);
        intersectPoints.addAll(intersectPoints(points, pointe));
        for (Point2D.Double p : this.getBoundary()) {
            if (polygon.contains(p)) {
                intersectPoints.add(p);
            }
        }
        for (Point2D.Double p : polygon.getBoundary()) {
            if (this.contains(p)) {
                intersectPoints.add(p);
            }
        }
        for (Point2D.Double p : intersectPoints) {
            Polygon pc = new Polygon(new Circle(p, 1));
            List<Point2D.Double> inpoints = new ArrayList<Point2D.Double>();
            for (Point2D.Double p1 : pc.getBoundary()) {
                if (this.contains(p1) && polygon.contains(p1)) {
                    inpoints.add(p1);
                }
            }
            if (inpoints.size() > 2) {
                Point2D.Double selectp = inpoints.get(inpoints.size() / 2);
                return sort(selectp, intersectPoints);
            }
        }
        return null;
    }

    private Polygon sort(Point2D.Double pi, Set<Point2D.Double> intersectPoints) {
        Map<String, Point2D.Double> treeMap = new TreeMap<String, Point2D.Double>();
        for (Point2D.Double p : intersectPoints) {
            if (p.equals(pi)) {
                continue;
            }
            double calculateAngle = Geography.calculateAngle(pi.x, pi.y, p.x, p.y);
            String[] split = (calculateAngle + "").split("\\.");
            String fixlength = StringUtil.addAtFirst2Fixlength(split[0], "0", 30) + "." + split[1];
            treeMap.put(fixlength, p);
        }
        List<Point2D.Double> a = new ArrayList<Point2D.Double>();
        for (Map.Entry<String, Point2D.Double> entry : treeMap.entrySet()) {
            a.add(entry.getValue());
        }
        return new Polygon(a);
    }

    /**
     * 求多边形与某条线段的交点
     *
     * @param polygon
     * @param point1
     * @param point2
     * @return
     */
    public Set<Point2D.Double> intersectPoints(Point2D.Double point1, Point2D.Double point2) {
        Set<Point2D.Double> ps = new HashSet<Point2D.Double>();//相交点
        Point2D.Double pointls = Geography.longilati2Decare(this.getPeakPoint(), point1);
        Point2D.Double pointle = Geography.longilati2Decare(this.getPeakPoint(), point2);
        Line line = new Line(pointls, pointle);
        for (int m = 0; m < this.getBoundaryConvert().size() - 1; m++) {
            Point2D.Double points = this.getBoundaryConvert().get(m);
            Point2D.Double pointe = this.getBoundaryConvert().get(m + 1);
            Line line2 = new Line(points, pointe);
            Point2D.Double intersectionPoint = line.getIntersectPoint(line2);
            if ((intersectionPoint != null) && (CommonUtil.between(intersectionPoint.x, points.x, pointe.x)) && (CommonUtil.between(intersectionPoint.y, points.y, pointe.y))) {
                if ((CommonUtil.between(intersectionPoint.x, pointls.x, pointle.x)) && (CommonUtil.between(intersectionPoint.y, pointls.y, pointle.y)) && (CommonUtil.between(intersectionPoint.x, points.x, pointe.x)) && (CommonUtil.between(intersectionPoint.y, points.y, pointe.y))) {
                    ps.add(Geography.decare2Longilati(this.getPeakPoint(), intersectionPoint));
                }
            }
        }
        Point2D.Double points = this.getBoundaryConvert().get(this.getBoundaryConvert().size() - 1);
        Point2D.Double pointe = this.getBoundaryConvert().get(0);
        Line line2 = new Line(points, pointe);
        Point2D.Double intersectionPoint = line.getIntersectPoint(line2);
        if ((intersectionPoint != null) && (CommonUtil.between(intersectionPoint.x, points.x, pointe.x)) && (CommonUtil.between(intersectionPoint.y, points.y, pointe.y))) {
            if ((CommonUtil.between(intersectionPoint.x, pointls.x, pointle.x)) && (CommonUtil.between(intersectionPoint.y, pointls.y, pointle.y)) && (CommonUtil.between(intersectionPoint.x, points.x, pointe.x)) && (CommonUtil.between(intersectionPoint.y, points.y, pointe.y))) {
                ps.add(Geography.decare2Longilati(this.getPeakPoint(), intersectionPoint));
            }
        }
        return ps;
    }

    @Deprecated
    public Point2D.Double getCenterPoint() {
        Point2D.Double point0 = getBoundaryConvert().get(0);
        Point2D.Double point1 = getBoundaryConvert().get(1);
        Point2D.Double point2 = getBoundaryConvert().get(getBoundaryConvert().size() - 1);
        Line line1 = new Line(point0, point1);
        Line line2 = new Line(point0, point2);
        Line line3 = new Line(point1, point2);
        double a = (line1.getA() + line2.getA())
                / (1.0D - line1.getA() * line2.getA());
        double b = point0.y - a * point0.x;
        Line line4 = new Line(a, b);
        Point2D.Double intersectionPoint = line4.getIntersectPoint(line3);
        return Geography.decare2Longilati(getBoundary().get(0), intersectionPoint);
    }

    public static void main(String[] args) {

        String boundary = "117.145604 31.850797,117.149268 31.850836,117.152334 31.850827,117.152366 31.850828,117.152382 31.850826,117.15239 31.850815,117.152397 31.850742,117.152404 31.850731,117.152427 31.850729,117.15266 31.850729,117.152679 31.850731,117.152687 31.850737,117.152688 31.850746,117.152683 31.850824,117.152683 31.850835,117.152692 31.850841,117.152707 31.850847,117.153785 31.850883,117.154725 31.85092,117.156694 31.850969,117.158136 31.85096,117.159095 31.850936,117.159569 31.850939,117.160849 31.850947,117.161796 31.850936,117.166558 31.851005,117.166575 31.851005,117.166594 31.850997,117.166597 31.850989,117.166602 31.85092,117.16661 31.85091,117.166625 31.850906,117.166864 31.850907,117.166884 31.850916,117.166896 31.850931,117.166897 31.851001,117.166903 31.85101,117.166919 31.851018,117.167204 31.851021,117.167222 31.851014,117.167227 31.851008,117.167228 31.850997,117.167257 31.849867,117.168465 31.849901,117.168519 31.849887,117.16854 31.849862,117.16854 31.84983,117.168575 31.849249,117.16858 31.849229,117.168599 31.849217,117.168618 31.849217,117.168645 31.849229,117.169047 31.849463,117.169157 31.849525,117.169294 31.84958,117.169404 31.849616,117.169927 31.84978,117.170997 31.850049,117.171013 31.850058,117.171032 31.850074,117.171043 31.850104,117.171144 31.850976,117.171166 31.851008,117.171195 31.851029,117.171241 31.851045,117.17133 31.851054,117.171721 31.85106,117.171949 31.851033,117.173046 31.851065,117.173108 31.851067,117.173277 31.851047,117.173816 31.850988,117.174575 31.85096,117.175114 31.850962,117.17553 31.85099,117.176021 31.851092,117.176163 31.851111,117.176305 31.85112,117.176933 31.851104,117.176965 31.851086,117.176981 31.851058,117.176986 31.851026,117.176994 31.850614,117.177 31.850584,117.177021 31.850566,117.178923 31.849981,117.179081 31.849933,117.179186 31.849889,117.179277 31.849846,117.179357 31.849794,117.179454 31.84973,117.179854 31.849472,117.179934 31.849438,117.180135 31.849359,117.180913 31.849076,117.180953 31.849065,117.180986 31.849062,117.181002 31.849067,117.181023 31.849083,117.181045 31.849103,117.181309 31.849479,117.181625 31.849837,117.181655 31.849857,117.181683 31.849867,117.181734 31.849872,117.181879 31.849873,117.181901 31.84987,117.181923 31.849859,117.181939 31.849838,117.181951 31.849807,117.182111 31.849232,117.18218 31.848969,117.182219 31.848778,117.182247 31.84874,117.182776 31.848591,117.183035 31.848616,117.184625 31.850564,117.184816 31.850826,117.184703 31.851497,117.184704 31.851512,117.184725 31.851525,117.184758 31.851534,117.185233 31.851611,117.185941 31.85169,117.186597 31.851794,117.186628 31.851794,117.186641 31.85179,117.186657 31.851782,117.1867 31.851749,117.186721 31.851712,117.187037 31.850902,117.187318 31.850348,117.187391 31.850148,117.187466 31.849879,117.187519 31.849599,117.18753 31.849476,117.187535 31.849332,117.187588 31.848076,117.187596 31.848052,117.187608 31.848039,117.187623 31.848029,117.187643 31.848022,117.187682 31.848012,117.187731 31.848005,117.1881 31.848001,117.190289 31.847994,117.191343 31.847985,117.193017 31.847981,117.1936 31.847972,117.193753 31.847898,117.194693 31.847876,117.194706 31.84787,117.19471 31.847863,117.194712 31.847853,117.194712 31.845362,117.19472 31.84308,117.194735 31.840517,117.194673 31.836184,117.194673 31.83617,117.194662 31.83615,117.194641 31.836136,117.194511 31.836122,117.194492 31.836116,117.194461 31.836096,117.194383 31.836028,117.194259 31.835857,117.194216 31.835744,117.194177 31.835164,117.194175 31.835143,117.194169 31.835132,117.194162 31.835126,117.194149 31.83512,117.194129 31.835115,117.19409 31.835111,117.193981 31.83511,117.193034 31.835176,117.192534 31.835211,117.192306 31.835214,117.192279 31.835217,117.192262 31.83522,117.192247 31.835224,117.19224 31.83523,117.192225 31.835244,117.192216 31.835266,117.192211 31.835291,117.192195 31.835682,117.192183 31.835791,117.192173 31.835807,117.19216 31.835818,117.192136 31.835825,117.190491 31.83597,117.190466 31.835971,117.190447 31.835971,117.190422 31.835964,117.190403 31.835949,117.190388 31.835925,117.19038 31.835895,117.190364 31.835411,117.190403 31.834796,117.190461 31.834229,117.190487 31.833936,117.190487 31.833915,117.190474 31.833899,117.190455 31.83389,117.190026 31.833849,117.189218 31.833435,117.188135 31.83307,117.187349 31.832815,117.187268 31.832774,117.187236 31.832737,117.187183 31.832641,117.187158 31.832612,117.187121 31.832589,117.187073 31.832573,117.185587 31.832559,117.185538 31.832559,117.18552 31.832555,117.18549 31.832528,117.185482 31.832493,117.185367 31.831999,117.185351 31.831965,117.185329 31.831949,117.185305 31.831942,117.185257 31.83194,117.182497 31.831935,117.180035 31.831951,117.178393 31.831944,117.177787 31.831983,117.177162 31.831972,117.175625 31.831928,117.174527 31.831919,117.174531 31.831552,117.174604 31.831437,117.174631 31.831256,117.174645 31.831235,117.174657 31.831225,117.174673 31.83122,117.174704 31.831216,117.175461 31.831206,117.175485 31.831199,117.175495 31.831189,117.1755 31.831168,117.175502 31.831134,117.175504 31.830844,117.175492 31.830829,117.175477 31.830822,117.175439 31.830821,117.174545 31.830838,117.174521 31.830858,117.174497 31.831278,117.174478 31.8313,117.174468 31.831305,117.174445 31.831307,117.17437 31.831305,117.174363 31.831305,117.17435 31.831308,117.174344 31.831313,117.174342 31.831325,117.174338 31.831891,117.174336 31.831901,117.174327 31.831913,117.174311 31.831923,117.174297 31.831924,117.171847 31.831941,117.170326 31.83196,117.169793 31.832013,117.168189 31.832019,117.167003 31.831982,117.164771 31.831818,117.163449 31.83172,117.156054 31.831173,117.155968 31.831164,117.155915 31.831166,117.155858 31.831182,117.155821 31.831205,117.155767 31.831259,117.153396 31.834249,117.151712 31.836738,117.151165 31.837658,117.149673 31.840265,117.148257 31.843236,117.146809 31.847,117.146031 31.84937,117.145548 31.850732,117.145548 31.85075,117.145556 31.850766,117.145572 31.850785,117.145604 31.850797";

        Polygon polygon = new Polygon(boundary);

        long start = System.currentTimeMillis();
        boolean contains = polygon.contains(118.152334,31.850827);
        long end = System.currentTimeMillis();
        System.out.println(end - start);

        System.out.println(contains);

    }
}
